//#region 打家劫舍 系列 （相邻背包不取）

import { TreeNode } from "../../utils/treeUtil";

/**198. 打家劫舍 - 普通
 * - 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 * - 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 */
export function rob(nums: number[]): number {
    // /*
    //   决定dp[i]的因素就是第i房间偷还是不偷。 
    //   如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。 
    //   如果不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点） 
    //   然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    // */
    /**dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。 */
    const dp = new Array(nums.length).fill(0)
    dp[0] = nums[0]; //因为递推公式依赖于dp[0] 和 dp[1]，所以需要进行初始化 
    dp[1] = Math.max(nums[0], nums[1])//偷0或偷1的最大值 

    for (let i = 2; i < nums.length; i++) {//从2开始，因为 0 1已经赋值了
        dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1])
        //                      偷i              不偷i  
    }
    return dp[nums.length - 1]

    //优化： 分析上面的可以看到，基本只会依赖前两个数字，所以可以不用数组存储，减少空间 
    let last2 = nums[0] //前第二个房子
    let last1 = Math.max(nums[0], nums[1] || nums[0]) //前第一个房子 （注意这里num1可能为undefined，直接求max会得到NaN，所以进行了处理）
    let max = last1
    for (let i = 2; i < nums.length; i++) {
        max = Math.max(last2 + nums[i], last1)
        last2 = last1
        last1 = max
    }
    return max
}
/**213. 打家劫舍 II - 环形 
 * - 这个地方所有的房屋都 围成一圈
 * - 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警
 * - 给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额
 */
export function rob2(nums: number[]): number {
    /*
      与打家劫舍I几乎一样，只不过成环了。
      那么我们需要修改的就是， 1. 考虑包含首元素，不包含尾元素   2. 考虑包含尾元素，不包含首元素。 
      也就是把nums给分成两种可能，然后分别计算一次打家劫舍，取最大值即可
    */

    if (nums.length == 0) return 0;
    if (nums.length == 1) return nums[0];


    const robFn = (arr: number[]): number => {
        /**dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。 */
        const dp = new Array(arr.length).fill(0)
        dp[0] = arr[0]; //因为递推公式依赖于dp[0] 和 dp[1]，所以需要进行初始化 
        dp[1] = Math.max(arr[0], arr[1])//偷0或偷1的最大值 

        for (let i = 2; i < arr.length; i++) {//从2开始，因为 0 1已经赋值了
            dp[i] = Math.max(dp[i - 2] + arr[i], dp[i - 1])
            //                      偷i              不偷i  
        }
        return dp[arr.length - 1]
    }
    return Math.max(robFn(nums.slice(0, -1)), robFn(nums.slice(1))) //分为两种情况
}
/**337. 打家劫舍 III - 树形DP基础题目
 * - 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
 * - 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
 * - 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
 */
export function rob3(root: TreeNode | null): number {
    /** [0] -> 不偷 、 [1] -> 偷 */
    /**递归函数。需要使用后序遍历！ */ //偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。
    const dfs = (node: TreeNode | null): [number, number] => {
        if (!node) return [0, 0]
        //深度优先（后序遍历）
        const left = dfs(node.left)
        const right = dfs(node.right)
        /**不偷当前的 */
        const res1 = Math.max(...left) + Math.max(...right) //选取左右最大值
        /**偷当前的 */
        const res2 = node.val + left[0] + right[0] //偷了当前的，就不能选下一个节点了
        return [res1, res2]
    }
    return Math.max(...dfs(root))
}
/**1388. 3n 块披萨 
 * - 给你一个披萨，它由 3n 块不同大小的部分组成，现在你和你的朋友们需要按照如下规则来分披萨： 
 * - 你每次可以任选披萨，然后你的两个朋友会拿走你选的那块的旁边两块
 * - 每一块披萨的大小按顺时针方向由循环数组 slices 表示。
 * - 请你返回你可以获得的披萨大小总和的最大值。
 */
export function maxSizeSlices(slices: number[] = [1, 2, 3, 4, 5, 6]): number {
    //与打家劫舍2很像，一个环形房屋，不能偷窃相邻的两家, 而且是环形，所以分类讨论，避免环形影响
    //分类：把环形转为非环形。假设数组长度为5，那么情况1就是考虑0~3，情况2是考虑 1~4，最后取最大值，这样就把整个数组覆盖到了
    // 但是这题要求，必须拿指定个数的披萨，所以需要比普通的打家劫舍的dp数组多一维，用第二维来控制拿的披萨数量


    /**每个人能选择的披萨数量  */
    const count = Math.floor(slices.length / 3);

    /**假设不循环，能取多少披萨
     * @param arr 传入截取后的数组。（原本循环，截取为两种情况，就可以看做不循环了）
     * @returns 披萨最大的大小
     */
    const robFn = (arr: number[]) => {
        const length = arr.length
        /**dp[i][j]：表示在前 i 个披萨中选择 j 个披萨的最大总大小*/
        const dp = Array.from({ length }, () => new Array(count + 1).fill(0))
        //初始化：递推公式需要这些数据
        dp[0][0] = 0;//一个都不取，肯定是0
        dp[0][1] = arr[0];//在0~0中取一个 
        dp[1][0] = 0;//在0~1中一个也不取
        dp[1][1] = Math.max(arr[0], arr[1]);//在0~1中取一个最大的
        for (let i = 2; i < length; i++) {//从2开始，因为地推公式需要
            for (let j = 1; j <= count; j++) {//取的披萨数量，从 1~count 
                dp[i][j] = Math.max(dp[i - 1][j], dp[i - 2][j - 1] + arr[i]);
                //                  不拿当前的      拿当前的 
            }
        }

        return dp[length - 1][count]
    }
    return Math.max(robFn(slices.slice(0, -1)), robFn(slices.slice(1)))//截成两个不循环的数组，覆盖所有情况，然后取最大值
}

//#endregion
